#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
class Solution
{
  public:
    int mem[N];
    int dfs(string &s, int x)
    {
        int n = s.size();
        if (n == x)
            return 1;
        if (s[x] == '0')
            return 0;
        if (mem[x])
            return mem[x];
        // 单个解码
        int res = dfs(s, x + 1);
        // 两个解码
        if (x + 1 < n)
        {
            int two = ((s[x] - '0') * 10) + (s[x + 1] - '0');
            if (two >= 10 && two <= 26)
            {
                res += dfs(s, x + 2);
            }
        }
        return mem[x] = res;
    }
    int numDecodings(string s)
    {
        int res = 0;
        int n = s.size();
        if (n == 0 || s[0] == '0')
            return 0;
        // vector<int> dp(n + 1, 0);
        // dp[0] = 1;
        // dp[1] = s[0] != '0' ? 1 : 0;
        int prevPrev = 1;
        int prev = s[0] != '0' ? 1 : 0;
        for (int i = 2; i <= n; i++)
        {
            int cur = 0;
            if (s[i - 1] != '0')
                cur += prev;
            // dp[i] += dp[i - 1];
            int two = ((s[i - 2] - '0') * 10) + (s[i - 1] - '0');
            if (two >= 10 && two <= 26)
            {
                // dp[i] += dp[i - 2];
                cur += prevPrev;
            }
            prevPrev = prev;
            prev = cur;
        }
        return prev;
        // return dp[n];
    }
};
// cur prev prePrev
//  2  1    0
//  3  2    1
//  